package 排序.utils;

/**
 * @author: yangwk
 * @date: 2023/4/11
 * @description:
 **/
public class HeapSort {
    public static void main(String[] args) {
        HeapSort heapSort = new HeapSort();
        int[] arr = new int[]{2, 1, 2, 1, 3};
        heapSort.heapSort(arr);
        System.out.println(arr);
    }

    public void heapSort(int[] arr) {
        Heap heap = new Heap(arr.length, true);
        for (int i : arr) {
            heap.insert(i);
        }
        for (int i = 0; i < arr.length; i++) {
            arr[i] = heap.delMax();
        }
    }

    class Heap {
        int[] arr;
        boolean desc;
        int N;

        public Heap(int N, boolean desc) {
            this.desc = desc;
            arr = new int[N + 1];
        }

        public int max() {
            return arr[1];
        }

        public int delMax() {
            int max = arr[1];
            arr[1] = arr[N--];
            sink(1);
            return max;
        }

        public void insert(int val) {
            this.N++;
            arr[N] = val;
            swim(N);
        }

        public void sink(int i) {
            while (i * 2 <= N) {
                int left = arr[i * 2];
                int max = i * 2;
                if (i * 2 + 1 <= N) {
                    int right = arr[i * 2 + 1];
                    max = bigger(left, right) ? i * 2 : i * 2 + 1;
                }
                if (bigger(arr[i], arr[max])) {
                    break;
                }
                swap(i, max);
                i = max;
            }
        }

        public void swim(int i) {
            while (i / 2 >= 1) {
                int father = i / 2;
                if (bigger(arr[father], arr[i])) {
                    break;
                }
                swap(father, i);
                i = father;
            }
        }

        public void swap(int i, int j) {
            int i1 = arr[i];
            int i2 = arr[j];
            arr[j] = i1;
            arr[i] = i2;
        }

        public boolean bigger(int i, int j) {
            return (i - j) * (desc == true ? 1 : -1) > 0;
        }
    }
}
